package com.liuyfly.leetcode.questions;

import com.liuyfly.leetcode.util.LeetcodeUtil;

import java.util.Arrays;

/**
 * @author liuyangfang 2021/9/27 上午10:51
 */
public class Question0704 {

    /**
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的
     * target，如果目标值存在返回下标，否则返回 -1。 <br/>
     * <br/>
     * 链接：https://leetcode.cn/problems/binary-search
     */
    public static int search(Integer[] array, int target) {
        return search(array, target, 0, array.length - 1);
    }

    public static int search(Integer[] array, int target, int start, int end) {
        int middle = (start + end) / 2;
        if (middle == start || middle == end) {
            if (array[start] == target) {
                return start;
            } else if (array[end] == target) {
                return end;
            } else {
                return -1;
            }
        }
        if (array[middle] == target) {
            return middle;
        } else if (array[middle] > target) {
            return search(array, target, start, middle - 1);
        } else if (array[middle] < target) {
            return search(array, target, middle + 1, end);
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] array = LeetcodeUtil.generateArray(10, 20);
        //        Integer[] array = { 0, 1, 3, 4, 5, 6, 7, 10, 11, 18 };
        Arrays.sort(array);
        LeetcodeUtil.printArray(array);
        for (Integer item : array) {
            int cursor = search(array, item);
            System.out.println(cursor);
        }
    }
}
